package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-maximum-path-sum/">二叉树中的最大路径和 [困难]</a>
 *
 * @author zhenzicheng
 * @date 2022-07-06 19:02
 */
public class BinaryTreeMaximumPathSum_124 {

  int maxPathSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    maxPath(root);
    return maxPathSum;
  }

  public int maxPath(TreeNode root) {
    if (root == null) return 0;

    // 递归计算当前节点通往左子树节点值之和，负数直接抛弃
    int left = Math.max(0, maxPath(root.left));
    // 递归向右字数找，同上
    int right = Math.max(0, maxPath(root.right));

    // 动态规划找当前的最大值（最优解）
    maxPathSum = Math.max(maxPathSum, left + right + root.val);

    return Math.max(left, right) + root.val;
  }
}
